吴师兄学算法

# LeetCode 416、分割等和子集

# 一、题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

class Solution {
    public boolean canPartition(int[] nums) {

        // 使用 sum 来保存数组中全部元素的和
        int sum = 0;

        // 遍历 nums 数组
        for (int i = 0 ; i < nums.length ; i++){
            // 把 nums 数组上的所有元素值累加到 sum 上
            sum += nums[i];
        }

        // 如果发现 sum 为奇数，那么必然无法拆分为两个相等的整数
        if(sum % 2 == 1){
            // 所以无法将这个数组分割成两个子集，返回false
            return false;
        }

        // 获取数组的长度
        int n = nums.length;

        // 获取数组中全部元素之后的一半
        // 接下来需要在数组 nums 中寻找一些数字去拼凑为 target
        // 如果能找到一些数字之和为 target，那么剩下的数字之和也是 target
        int target = sum / 2;

        // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
        // dp[0][0] 表示 nums 的前 0 个元素能否可以组成和为 0 的结果
        // dp[2][6] 表示 nums 的前 2 个元素能否可以组成和为 6 的结果
        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // i 的值从 0 到 n - 1
        // j 的值从 0 到 target
        boolean[][] dp = new boolean[n][target + 1];

        // 先初始化  dp[0][nums[0]]
        // 如果 nums 的第 0 个元素 nums[0] 小于 target
        if (nums[0] <= target) {
            // 那么 nums 的前 0 个元素能否可以组成和为 nums[0] 的结果是 true
            // 因为 nums 的前 0 个元素就是 nums[0]
            dp[0][nums[0]] = true;
        }
        

        // 接下来开始往 dp 数组中填充结果
        // i 的值从 1 到 n - 1
        for (int i = 1; i < n; i++) {
            // j 的值从 0 到 target
            for (int j = 0; j <= target; j++) {
                // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                // 对于 dp[i][j] 来说，如果 dp[i - 1][j] 为 true，那么 dp[i][j] 必然也为 true
                // 所以，先初始化 dp[i][j] 的值为 dp[i - 1][j] 的值
                // 再通过后面的代码修改 dp[i][j] 中还为 false 的值 
                dp[i][j] = dp[i - 1][j];

                // 如果此时 nums[i] 恰巧为 j
                // 那么对于 dp[i][j] 来说，nums 的前 i 个元素可以组成和为 j 的结果
                if (nums[i] == j) {
                    // 所以 dp[i][j] 为 true
                    dp[i][j] = true;
                    // 同时继续
                    continue;
                }

                // 如果发现 nums[i] 小于 j
                if (nums[i] < j) {
                    // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j - nums[i]] 表示 nums 的前 i - 1 个元素能否可以组成和为 j - nums[i] 的结果
                    // 那么 dp[i][j] 的结果要为 true
                    // 1、nums 的前 i - 1 个元素可以组成和为 j 
                    // 2、nums 的前 i - 1 个元素可以组成和为 j - nums[i]
                    // 对于 1 来说，不用使用 nums[i] 就组成了 j
                    // 对于 2 来说，前 i - 1 个元素可以组成和为 j - nums[i]，那么加上此时的值 nums[i]，也组成了 j
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }

        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // 返回这个结果
        return dp[n - 1][target];

    }
}

# **2、**C++ 代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 使用 sum 来保存数组中全部元素的和
        int sum = 0;

        // 遍历 nums 数组
        for (int i = 0 ; i < nums.size() ; i++){
            // 把 nums 数组上的所有元素值累加到 sum 上
            sum += nums[i];
        }

        // 如果发现 sum 为奇数，那么必然无法拆分为两个相等的整数
        if(sum % 2 == 1){
            // 所以无法将这个数组分割成两个子集，返回false
            return false;
        }

        // 获取数组的长度
        int n = nums.size();

        // 获取数组中全部元素之后的一半
        // 接下来需要在数组 nums 中寻找一些数字去拼凑为 target
        // 如果能找到一些数字之和为 target，那么剩下的数字之和也是 target
        int target = sum / 2;

        // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
        // dp[0][0] 表示 nums 的前 0 个元素能否可以组成和为 0 的结果
        // dp[2][6] 表示 nums 的前 2 个元素能否可以组成和为 6 的结果
        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // i 的值从 0 到 n - 1
        // j 的值从 0 到 target
        auto dp = vector < vector < bool>> ( n ,vector<bool> (target + 1));

        // 先初始化  dp[0][nums[0]]
        // 如果 nums 的第 0 个元素 nums[0] 小于 target
        if (nums[0] <= target) {
            // 那么 nums 的前 0 个元素能否可以组成和为 nums[0] 的结果是 true
            // 因为 nums 的前 0 个元素就是 nums[0]
            dp[0][nums[0]] = true;
        }
        

        // 接下来开始往 dp 数组中填充结果
        // i 的值从 1 到 n - 1
        for (int i = 1; i < n; i++) {
            // j 的值从 0 到 target
            for (int j = 0; j <= target; j++) {
                // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                // 对于 dp[i][j] 来说，如果 dp[i - 1][j] 为 true，那么 dp[i][j] 必然也为 true
                // 所以，先初始化 dp[i][j] 的值为 dp[i - 1][j] 的值
                // 再通过后面的代码修改 dp[i][j] 中还为 false 的值 
                dp[i][j] = dp[i - 1][j];

                // 如果此时 nums[i] 恰巧为 j
                // 那么对于 dp[i][j] 来说，nums 的前 i 个元素可以组成和为 j 的结果
                if (nums[i] == j) {
                    // 所以 dp[i][j] 为 true
                    dp[i][j] = true;
                    // 同时继续
                    continue;
                }

                // 如果发现 nums[i] 小于 j
                if (nums[i] < j) {
                    // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j - nums[i]] 表示 nums 的前 i - 1 个元素能否可以组成和为 j - nums[i] 的结果
                    // 那么 dp[i][j] 的结果要为 true
                    // 1、nums 的前 i - 1 个元素可以组成和为 j 
                    // 2、nums 的前 i - 1 个元素可以组成和为 j - nums[i]
                    // 对于 1 来说，不用使用 nums[i] 就组成了 j
                    // 对于 2 来说，前 i - 1 个元素可以组成和为 j - nums[i]，那么加上此时的值 nums[i]，也组成了 j
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }

        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // 返回这个结果
        return dp[n - 1][target];
    }
};

# 3、Python 代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 使用 total 来保存数组中全部元素的和
        total = sum(nums)

        # 如果发现 sum 为奇数，那么必然无法拆分为两个相等的整数
        if total & 1:
            return False

        # 获取数组的长度
        n = len(nums)

        # 获取数组中全部元素之后的一半
        # 接下来需要在数组 nums 中寻找一些数字去拼凑为 target
        # 如果能找到一些数字之和为 target，那么剩下的数字之和也是 target
        target = total // 2

        # dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
        # dp[0][0] 表示 nums 的前 0 个元素能否可以组成和为 0 的结果
        # dp[2][6] 表示 nums 的前 2 个元素能否可以组成和为 6 的结果
        # dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        # i 的值从 0 到 n - 1
        # j 的值从 0 到 target
        dp = [[False] * (target + 1) for _ in range(n)]

        # 先初始化  dp[0][nums[0]]
        # 如果 nums 的第 0 个元素 nums[0] 小于 target
        if  nums[0] <= target : 
            # 那么 nums 的前 0 个元素能否可以组成和为 nums[0] 的结果是 true
            # 因为 nums 的前 0 个元素就是 nums[0]
            dp[0][nums[0]] = True
        

        # 接下来开始往 dp 数组中填充结果
        # i 的值从 1 到 n - 1
        for i in range( 1 , n ):
            # j 的值从 0 到 target
            for j in range( 0 , target + 1 ):
                # dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                # dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                # 对于 dp[i][j] 来说，如果 dp[i - 1][j] 为 true，那么 dp[i][j] 必然也为 true
                # 所以，先初始化 dp[i][j] 的值为 dp[i - 1][j] 的值
                # 再通过后面的代码修改 dp[i][j] 中还为 false 的值 
                dp[i][j] = dp[i - 1][j]

                # 如果此时 nums[i] 恰巧为 j
                # 那么对于 dp[i][j] 来说，nums 的前 i 个元素可以组成和为 j 的结果
                if nums[i] == j  : 
                    # 所以 dp[i][j] 为 true
                    dp[i][j] = True
                    # 同时继续
                    continue
                

                # 如果发现 nums[i] 小于 j
                if nums[i] < j : 
                    # dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                    # dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                    # dp[i - 1][j - nums[i]] 表示 nums 的前 i - 1 个元素能否可以组成和为 j - nums[i] 的结果
                    # 那么 dp[i][j] 的结果要为 true
                    # 1、nums 的前 i - 1 个元素可以组成和为 j 
                    # 2、nums 的前 i - 1 个元素可以组成和为 j - nums[i]
                    # 对于 1 来说，不用使用 nums[i] 就组成了 j
                    # 对于 2 来说，前 i - 1 个元素可以组成和为 j - nums[i]，那么加上此时的值 nums[i]，也组成了 j
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]


        # dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        # 返回这个结果
        return dp[n - 1][target]

← LeetCode 474、一和零 →